package com.hackerank.arrays.map;

import java.util.HashMap;
import java.util.Map;

/***
 *  Hash Tables: Ransom Note
 *  https://www.hackerrank.com/challenges/ctci-ransom-note/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps
 *
 *  题目大意：
 *
 *  1、一个人想做一篇文档，文档里的词都是从杂志里剪下来的。
 *  2、输入两个字符串数组，第一个数组存放杂志原文，每个元素代表一个单词；第二个数组是要做成的文档
 *  3、如果杂志里的单词能够完成文档，则输出 Yes，无法完成则输出No
 *  4、注意：杂志里的每个单词只能用一次，如杂志中只出现过一次some，而文档中有两个some，则输出No，但是杂志中有多个some，文档只用一次可以。
 *
 * 解题思路：Map保存word，并记录次数
 * 时间复杂度 O(m + n)
 * 空间复杂度 O(m)
 * */
public class RansomNote {

    static void checkMagazine(String[] magazine, String[] note) {
        if(note.length > magazine.length){
            System.out.println("No");
            return;
        }
        Map<String,Integer> words = new HashMap<String,Integer>();

        for(int i=0;i<magazine.length;i++){
            String word = magazine[i];
            Integer c = words.get(word);
            c = c==null ? 1 : c+1;
            words.put(word,c);
        }

        for(int j=0;j<note.length;j++){
            String word = note[j];
            Integer c = words.get(word);
            if(c == null || c==0){
                System.out.println("No");
                return;
            }else{
                words.put(word,c-1);
            }
        }

        System.out.println("Yes");
    }

}
